1. Field of the Invention
The present invention relates to a receiving apparatus and method and a program and, more particularly, to a receiving apparatus and method and a program that are configured to reduce the circuit scale of the receiving apparatus more than ever while maintaining the decoding performance of the receiving apparatus.
2. Description of the Related Art
In communication system, reliable communication over communication channels having noise is assured by use of coding. For example, with a wireless system, such as an satellite network, there are many noise sources due to geographical and environmental factors. These communication channels are representative of fixed capacities and specify a theoretical upper limit known as the Shannon limit that can represent bits per symbol in a certain signal-to-noise ratio (SNR). As a result, the purpose of coding designs is to achieve rates that close in on this Shannon limit. Especially, this purpose is closely related with bandwidth-restrictive satellite systems.
In recent years, coding techniques having performances close to the Shannon limit have been developed, such as PCCC (Parallel Concatenated Convolution Codes) and SCCC (Serially Concatenated Convolution Codes), for example, which are referred to as so-called turbo coding. Along with the development of these turbo coding techniques, LDPC (Low Density Parity Check codes) that have been known since a long time ago are attracting attention.
The LDPC coding was first proposed in “Low Density Parity Check Codes,” Cambridge, Mass.; M.I.T. Press, 1963 by R. G. Gallager and subsequently attracted attention again in “Good error correcting codes based on very parse matrices,” Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999 by D. J. C. MacKay and “Analysis of low density codes and improved designs using irregular graphs,” in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998 by M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spileman and the like.
Recent studies indicate that, like the turbo coding, the LDPC coding provides a performance close to the Shannon limit as code length is increased. Also, since the LDPC coding has a property that minimum distance is proportional to code length, the LDPC coding is good in block error probability characteristic and involves little error floor phenomenon that is observed in the decoding characteristic of turbo codes and so on.
The following specifically describes the LDPC coding. It should be noted that the LDPC coding is linear coding and need not always be binary but, in the following description, the LDPC coding is assumed to be binary.
The greatest characteristic of the LDPC coding is that a parity check matrix for defining a particular LDPC code is sparse. A sparse matrix is a matrix in which the number of “1s,” a component of the matrix, is very small. Let a sparse parity check matrix be H, then such a parity check matrix H includes one in which a hamming weight (the number of “1s”) of each row is “3” and a hamming weight of each column is “6”), for example.
Thus, the LDPC coding defined by parity check matrix H with the hamming weights of rows and columns being constant is referred to as regular LDPC coding. On the other hand, the LDPC coding defined by parity check matrix H with the hamming weights of rows and columns being not constant is referred to as irregular LDPC coding.
The above-mentioned coding by the LDPC coding is realized by generating a generator matrix G on the basis of the parity check matrix H and multiplying a binary information message by the obtained generator matrix G to generate a code word. To be more specific, a coding apparatus for executing coding based on he LDPC coding first calculates a generator matrix G in which equation GHT=0 is established with a transposed matrix HT of the parity check matrix H. Here, if the generator matrix G is a k×n matrix, the coding apparatus multiplies the generator matrix G by a k-bit information message (vector u) to generate an n-bit code word c (=uG). With the code word generated by the coding apparatus, a code bit having value “0” is mapped to “+1,” a code bit having value “1” is mapped to “−1,” and so on. The mapped code word is transmitted to a receiving side through a predetermined communication path.
On the other hand, the decoding of LDPC codes is an algorithm proposed by Gallager as probabilistic decoding, which can be executed a message passing algorithm based on belief propagation on the so-called Tanner graph that is made up of a variable node (also referred to as a message node) and a check node. In what follows, the variable node and the check node will be generically referred to simply as a node.
However, in the probabilistic decoding, a message transferred between nodes is a real value, so that an analytical solution requires the tracing of the probabilistic distribution itself of a message that takes continuous values, which is very difficult to execute. Therefore, Gallager proposed algorithm A or algorithm B as an LDPC-code decoding algorithm.
The decoding of LDPC codes is executed by a following procedure shown in FIG. 2, for example. It is assumed that receive data i of an LDPC code having a length of code length be U0(u0i), message j (a message outputted from edge j connected to the check node) outputted from the check node be uj, and message i (a message outputted from edge i connected to the variable node) outputted from the variable node be vj. It should be noted that a message denotes a real value representative of a so-called log likelihood ratio and so on indicative of “0” likelihood of a value.
First, in the decoding of LDPC codes, as shown in FIG. 2, receive data U0(u0i) is received in step S11, message uj is initialized to “0,” and variable k that takes an integer as a repetitive processing counter is initialized to “0,” upon which the procedure goes to step S12. In step S12, message vj is obtained by executing the operation of a variable node indicated in equation (1) below by use of receive data U0(u0i) and, by use of this message vj, message uj is obtained by computing a check node indicated in equation (2) below.
                    [                  Equation          ⁢                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                [                  Equation          ⁢                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
In equation (1) and equation (2) above, dv and dc are selectable parameters indicative of the number of “1s” in the vertical (or column) direction and the horizontal (or row) direction, namely, a column weight (or hamming weight) and a row weight, of parity check matrix H, respectively. For example, in the case of (3, 6) code, dv=3 and dc=6.
It should be noted that, in the operation of equation (1) or equation (2), a message entered from the edge from which a message is to be outputted is not used as an object of sum or product operation, so that a range of sum or product operation is 1 to dy−1 or 1 to dc−1. The operation indicated by equation (2) can be executed by creating a table of function R(v1, v2) indicated in equation (3) below for obtaining 1 for two inputs v1, v2 in advance and using this table recursively as shown in equation (4) below.
                    [                  Equation          ⁢                                          ⁢          3                ]                                                                                                x              =                            ⁢                              2                ⁢                                  tanh                                      -                    1                                                  ⁢                                  {                                                            tanh                      ⁡                                              (                                                                              v                            1                                                    2                                                )                                                              ⁢                                          tanh                      ⁡                                              (                                                                              v                            2                                                    2                                                )                                                                              }                                                                                                        =                            ⁢                              R                ⁡                                  (                                                            v                      1                                        ,                                          v                      2                                                        )                                                                                        (        3        )                                [                  Equation          ⁢                                          ⁢          4                ]                                                                                                x              =                            ⁢                              2                ⁢                                  tanh                                      -                    1                                                  ⁢                                  {                                                            tanh                      ⁡                                              (                                                                              v                            1                                                    2                                                )                                                              ⁢                                          tanh                      ⁡                                              (                                                                              v                            2                                                    2                                                )                                                                              }                                                                                                        =                            ⁢                              R                ⁡                                  (                                                            v                      1                                        ,                                          v                      2                                                        )                                                                                        (        4        )            
In step S12, variable k is incremented by “1” and the procedure goes to step S13. In step S13, it is determined whether variable k is greater than predetermined repetitive decoding count N. If variable k is found not greater than N in step S13, then the procedure returns to step S12 to repeat the processing therefrom.
If variable k is found to be greater than N in step S13, then the procedure goes to step S14, in which message v as a decoding result to be finally outputted by executing the operation indicated in equation (5) below is obtained and message v thus obtained is outputted, upon which the LDPC code decoding comes to an end.
                    [                  Equation          ⁢                                          ⁢          5                ]                                                            v        =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Unlike the operation of equation (1), the operation of equation (5) is executed by use of message uj from all edges connected to the variable node.
In this LDPC code decoding, in the case of code (3, 6) for example, messages are transferred between nodes as shown in FIG. 3. It should be noted that, in FIG. 3, each node indicated by “=” (equal) denotes a variable node, in which variable node operation indicated by equation (1) is executed. Each node indicated by “+” (plus) in FIG. 3 denotes a check note, in which check node operation indicated by equation (2) is executed. Especially, in algorithm A, a message is binarized, an exclusive OR operation of dc−1 input messages (messages vi to be entered in check nodes) is executed at the check nodes indicated by “+K” and, if all of dv−1 input messages (messages uj to be entered in variable nodes) have different bit values for receive data R at the variable nodes indicated by “=,” the messages are outputted with signs inverted.
Recently, studies of methods of mounting LDPC code decoding have also been being carried out. Before explaining mounting methods, the decoding of LDPC codes will be described in a schematic manner.
Referring to FIG. 4, there is shown an example of parity check matrix H of LDPC code (coding ratio=1/2, code length=12) of code (3, 6). Parity check matrix H of LDPC codes may be written as shown in FIG. 5 by use of the Tannar graph. Referring to FIG. 5, each node indicated by “+” is a check node and each node indicated by “=” is a variable node. The check nodes and the variable nodes correspond to the row and the column of parity check matrix H, respectively. Each of the connections between the check nodes and the variable nodes is an edge, being equivalent to “1” of parity check matrix H. Namely, if the component of j row, i column of parity check matrix H is 1, then, in FIG. 5, i variable node (node indicated by “=”) from top and j check node (node indicated by “+”) from top are interconnected by an edge. An edge denotes that the bit of an LDPC code (of receive data) corresponding to a variable node has a constraint condition corresponding to a check node. It should be noted that FIG. 5 shows the Tannar graph representation of parity check matrix H shown in FIG. 4.
The sum product algorithm, an LDPC code decoding algorithm, repetitively executes the operation of variable nodes and the operation of check nodes.
At variable nodes, the variable node operation shown in equation (1) is executed as shown in FIG. 6. Namely, in FIG. 6, message vi corresponding to i edge among the edges connected to the variable nodes is computed by use of messages u1 and u2 from the remaining edges connected to the variable nodes and receive data u0i. The messages corresponding to other edges are computed in the similar manner.
Before explaining the operation of check nodes, equation (2) is rewritten to equation (6) by use of a relation of a×b=exp {1n(|a|)+1n(|b|)}×sign(a)×sign (b), where sign(X) is 1 (logical 0) when x>0 and −(logical 1) when x<0.
                    [                  Equation          ⁢                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
Further, if nonlinear function φ(X)=−1n(tan h(x/2)) is defined with x≧0, inverse function φ−1(X) is expressed in φ−1(X)=2 tan h−1(e−x), so that equation (6) can be written as equation (7).
                    [                  Equation          ⁢                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                        d                                          c                      ⁢                                                                                          -                      1                                                                      ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
At each check node, the operation of check node indicated by equation (7) is executed as shown in FIG. 7. Namely, In FIG. 7, message uj corresponding to j edge among the edges connected to the check nodes is computed by use of messages v1, v2, v3, v4, v5 from the remaining edges connected to check nodes. The messages corresponding to the other edges are computed in the similar manner.
It should be noted that function φ(X) can be expressed as φ(X)=1n((ex+1)/(ex−1)). When x>0, φ(X)=φ−1(X), namely, an operation result of nonlinear function φ(X) is the same as an operation result of inverse function φ−1(X) thereof. In installing functions φ(X) and φ−1(X) on hardware, the installation may be made by use of a LUT (Look Up Table), which is common to both the functions.
It should also be noted that the variable node operation indicated by equation (1) can be divided into equation (5) and equation (8).[Equation 8]vi=v−udv  (8)
Therefore, repetitive execution of the operations of equation (5) and equation (8), and equation (7) can execute the repetitive execution of the operation of variable nodes of equation (1) and the operation of check nodes of equation (7).
In this case, as shown in FIG. 8, a result of the operation of equation (5) among variable node operations of equation (5) and equation (8) can be used as a final decoding result as it is.
If the sum product algorithm is installed on hardware to provide a decoding apparatus, it is necessary to repetitively execute variable node operations expressed in equation (1), equation (5) or equation (8) and check node operations expressed in equation (7) in a proper circuit scale and with a proper operating frequency.
The following describes, a decoding apparatus installation example, a method of installing full serial decoding for simply decoding the operations of nodes one by one sequentially.
Referring to FIG. 9, there is shown an exemplary configuration of a decoding apparatus for executing LDPC code decoding.
In the decoding apparatus shown in FIG. 9, a message corresponding to one edge is computed for every operation clock.
To be more specific, the decoding apparatus shown in FIG. 9 has a message calculating block 101, a message memory 104, a received value memory 105, and a control block 106. The message calculating block 101 is made up of a variable node calculator 102 and a check node calculator 103.
In the decoding apparatus shown in FIG. 9, messages are read from the message memory 104 to the message calculating block 101 one by one. In the message calculating block 101, by use of these messages, a message corresponding to a desired edge is computed, Then, the message obtained by this computation is stored in the message memory 104. In the decoding apparatus shown in FIG. 9, this processing executed repetitively. Namely, so-called repetitive decoding is executed.
To be more specific, the received value memory 105 is supplied with receive data (LDPC code) D100 that is logarithmic likelihood ratio indicative of likelihood of 0 (or 1) of a code that is obtained by receiving a transmitted LDPC code and the received value memory 105 stores this receive data D100.
At the time of a variable node operation, the received value memory 105 reads the stored receive data in accordance with a control signal supplied from the control block 106 and supplies the read receive data to the variable node calculator 102 of the message calculating block 101 as receive data D101.
Also, at the time of a variable node operation, the message memory 104 reads stored message (check node message uj) D102 in accordance with a control signal supplied from the control block 106 and supplies the read receive data to the variable node calculator 102. By use of the message D102 supplied from the message memory 104 and the receive data D101 supplied from the received value memory 105, the variable node calculator 102 executes the variable node operation of equation (1) and supplies message (variable node message) vi obtained as a result of this variable node operation to the message memory 104 as message D103.
Next, the message memory 104 stores the message D103 supplied from the variable node calculator 102.
On the other hand, at the time of a check node operation, the message memory 104 reads stored variable node message vj as message D104 in accordance with a control signal supplied from the control block 106 and supplies the read message to the check node calculator 103.
By use of the message D104 supplied from the message memory 104, the check node calculator 103 executes the check node operation of equation (7) and supplies message (check node message) uj obtained by this check node operation to the message memory 104 as message D105.
Then, the message memory 104 stores the message D105 supplied from the check node calculator 103.
The message D105 supplied by the check node calculator 103 from the message memory 104, namely, check node message uj is read as a message D102 at the time of a next variable node operation to be supplied to the variable node calculator 102.
Referring to FIG. 10, there is shown an exemplary configuration of the variable node calculator 102 shown in FIG. 9 that executes variable node operations one by one.
The variable node calculator 102 has two input ports P101 and P102 as inputs ports to which a message (data) is supplied (inputted) from the outside and one output port P103 as a port for supplying (outputting) a message to the outside. By use of messages entered through the input ports P101 and P102, the variable node calculator 102 executes the variable node operation of equation (1) and outputs a message obtained as a result of the operation from the output port P103.
To be more specific, the receive data D101 read from the received value memory 105 is supplied to the input port P101. The message D102 (check node message uj) read from the message memory 104 is supplied to the input port P102.
In the variable node calculator 102, messages D102 (message uj) from the check nodes corresponding to the rows of the parity check matrix are read from the input port P102 one by one to be supplied to an ALU (Arithmetic and Logic Unit) 151 and a FIFO memory 155. Also, in the variable node calculator 102, the receive data D101 is read from the received value memory 105 via the input port P101 one by one to be supplied to an ALU 157.
The ALU adds the message D102 (message uj) to a value D151 stored in a register 152 to integrate the message D102 and stores a resultant integrated value into the register 152 again. It should be noted that, when messages D102 from all edges over one column of the parity check matrix are integrated, the register 152 is set to 0.
If the messages D102 over one column of the parity check matrix are read one by one and an integrated value obtained by the integration of messages D102 for one column is stored in the register 152, namely, if an integrated value (Σuj from j=1 to dv) obtained by integrating messages D102 (messages uj) from all edges over one column of the parity check matrix is stored in the register 152, a selector 153 selects the value stored in the register 152, namely, integrated value D151 (Σuj from j=1 to dv) obtained by integrating messages D102 (message uj) from all edges over one column of the parity check matrix and stores the selected value into a register 154.
The register 154 supplies the stored value D151 to the selector 153 and an ALU 156 as value D152. Up to the point of time immediately before the value obtained by integrating messages D102 for one column is stored in the register 152, the selector 153 selects the value D152 supplied from the register 154 and stores the selected value into the register 154 again. Namely, until messages D102 (message uj) from all edges over one column of the parity check matrix have been integrated, the register 154 supplies the value obtained by the last integration to the selector 153 and the ALU 156.
On the other hand, a FIFO (First In First Out) memory 155 delays the message D102 from check nodes until a new value D152 (Σuj from j=1 to dv) is outputted from the register 154 and then supplies the new value D152 to the ALU 156 as a value D153. The ALU 156 subtracts the value D153 supplied from the FIFO memory 155 from the value D152 supplied from the register 154. To be more specific, the ALU 156 subtracts messages uj from edges to be obtained from the integrated value (Σuj from j=1 to dv) of messages D102 (message uj) of all edges over one column of the parity check matrix to obtain a subtracted value (Σuj from j=1 to dv−1), thereby supplying the obtained subtracted value to the ALU 157.
The ALU 157 adds the receive data D101 from the input port P101 to the subtracted value (Σuj from j=1 to dv) from the ALU 156 and outputs a resultant added value from the output port P103 as message D103 (message vj).
As described above, in the variable node calculator 102, the variable node operation (vi=u0i+Σuj) of equation (1) is executed and messages (variable node messages) vi obtained as a result of this operation are outputted from the output port P103.
Referring to FIG. 11, there is shown an exemplary configuration of the check node calculator 103 shown in FIG. 9 that executes check node operations one by one.
The check node calculator 103 has one input port P111 through which messages (data) are supplied (entered) from the outside and one output port P112 through which messages are supplied (outputted) to the outside. By use of messages entered through the input port P111, the check node calculator 103 executes the check node operation of equation (7), outputting messages obtained as a result of this operation from the output port P112.
Namely, the message D104 (variable node message vi) read from the message memory 104 is supplied to the input port P111.
In the check node calculator 103, messages D104 (messages vi) from the variable nodes corresponding to columns of the parity check matrix are read from the input port P111 one by one and the low-order bits except for the most significant bit, namely, absolute value D122 (|vi|) of message D104 is supplied to the LUT 121 and the most significant bit, namely, the sign bit (indicative of plus or minus) D121 of message D104 to an EXOR circuit 129 and a FIFO memory 133.
The LUT 121 outputs an operation result of nonlinear function φ(X) in the check node operation of equation (7) with a value entered in the LUT 121 being argument x. More particularly, the LUT 121 reads operation result D123 (φ(|vi|)) obtained by operating nonlinear function φ(|vi|) for the supply of absolute value D122 (|vi|) and supplies this operation result to an ALU 122 and a FIFO memory 127.
The ALU 122 adds the operation result D123 (φ(|vi|) to the value D124 stored in a register 123 to integrate the operation result D123 (φ(|vi|) and stores an integrated value obtained as a result of this integration into the register 123 again. It should be noted that, when the operation results D123 (φ(|vi|)) for the absolute values D122 (|vi|) of the messages D104 from all edges over one row of the parity check matrix have been integrated, then the register 123 is reset to 0.
When the messages D104 over one row of the parity check matrix have been read one by one and an integrated value obtained by integrating operation results D123 for one row is stored in the register 123, then a selector 124 selects the value stored in the register 123, namely, the integrated value D124 (Σφ(|vi|) from i=1 to dc) with φ(|vi|) obtained from messages D104 (messages vi) from all edges over one row of the parity check matrix integrated and then stores the selected integrated value D124 into a register 125 as a value D125. The register 125 supplies the stored value D125 to the selector 124 and an ALU 126 as a value D126.
Up to the point of time immediately before the integrated value obtained by integrating the operation results D123 for one row is stored in the register 123, the selector 124 selects the value D126 supplied from the register 125 and stores this value into the register 125 again. Namely, until φ(|vi|) obtained from the messages D104 (messages vi) from all edges over one row of the parity check matrix is integrated, the register 125 supplies the integrated value of φ(|vi|) integrated last to the selector 124 and the ALU 126.
On the other hand, the FIFO memory 127 delays the operation result D123 (φ(|vi|)) outputted from the LUT 121 until a new value D126 (Σφ(|vi|) from j=1 to dc) is outputted from the register 125 and then supplies the new value D126 to the ALU 126 as a value D172. The ALU 126 subtracts the value D127 supplied from the FIFO memory 127 from the value D126 supplied from the register 125 and supplies a subtraction result to a LUT 128 as a subtracted value D128. To be more specific, the ALU 126 subtracts φ(|vi|) obtained from messages (messages vi with i=dc) form edges to be obtained from the integrated value (Σφ(|vi|) from j=1 to dc) of φ(|vi|) of the messages D104 (message vi) of all edges over one row of the parity check matrix, thereby supplying the obtained subtracted value (Σφ(|vi|) from i=1 to dc−1) to the LUT 128 as a subtracted value D128.
The LUT 128 outputs an operation result of inverse function φ−1(X) of nonlinear function φ(X) in the check node operation of equation (7) with the value entered in the LUT 128 being argument X. More particularly, the LUT 128 outputs operation result D129 (φ−1(Σφ(|vi|))) obtained by operating inverse function φ−1(Σφ(|vi|)) on the supply of subtracted value D128 (Σφ(|vi| from i=1 to dc−1)) from the ALU 126.
It should be noted that, as described above, since the operation result of nonlinear function φ(X) and the operation result of inverse function φ−1(X) for the same argument X are equal, the LUT 121 and the LUT 128 have the same configuration.
Concurrently with the above-mentioned processing, the EXOR circuit 129 executes an exclusive OR operation between the value D131 stored in a register 130 and the sign bit D121 to make a multiplication between the sign bits of the message D104, storing a multiplication result in the register 130 again. It should be noted that when the sign bits D121 of messages D104 from all edges over one row of the parity check matrix have been multiplied, the register 130 is reset.
When the operation result D130 (Π sign(vi) from i=1 to dc) obtained by multiplying sign bits D121 of messages D104 from all edges over one row of the parity check matrix has been stored in the register 130, a selector 131 selects the value stored in the register 130, namely, the value D131 (Π sign(vi) from i=1 to dc) obtained by multiplying the sign bits D121 of the messages D104 from all edges over one row of the parity check matrix and stores the selected value into a register 132 as a value D132. The register 132 supplies the stored value D132 to the selector 131 and an EXOR circuit 134 as a value D133.
Up to the point immediately before the multiplication result D130 (Π sign(vi) from i=1 to dc) obtained by multiplying the sign bits D121 of the messages D104 from all edges over one row of the parity check matrix is stored in the register 130, the selector 131 selects the value D133 supplied from the register 132 and stores this value in the register 132 again. Namely, until the sign bits D121 of the messages D104 from all edges over one row of the parity check matrix are multiplied, the register 132 supplies the value stored last to the selector 131 and the EXOR circuit 134.
On the other hand, the FIFO memory 133 delays the sign bit D121 until a new value D133 (Π sign(vi) from i=1 to dc) is supplied from the register 132 to the EXOR circuit 134 and then supplies the delayed bit to the EXOR circuit 134 as 1-bit value D134. The EXOR circuit 134 executes an exclusive OR operation between the value D133 supplied from the register 132 and the value D134 supplied from the FIFO memory 133 to divide the value D133 by the value D134, outputting a division result as a value D135. Namely, the EXOR circuit 134 divides the multiplied value of the sign bits D121 (sign(vi)) of the messages D104 from all edges over one row of the parity check matrix by the sign bit D121 (sign (vi)) of the message D104 from an edge to be obtained, outputting the divided value (Π sign(vi) from i=1 to dc−1) as a divided value D135.
Then, in the check node calculator 103, a bit string with the operation result D129 outputted from the LUT 128 being the least significant bit and the divided value D135 outputted from the EXOR circuit 134 being the most significant bit (sign bit) is outputted from the output port P112 as a message D105 (message uj).
As described above, in the check node calculator 103, the operation of equation (7) is executed to obtain the message (check node message) uj.
It should be noted that, although not shown, in the decoding apparatus shown in FIG. 9, the operation of equation (5) is executed instead of the variable node operation of equation (1) at the final decoding stage (for example, a variable node operation that is executed last of the variable node operations and the check node operations that are executed by predetermined repetitive decoding count N, a result of this operation being outputted as the final decoding result.
According to the decoding apparatus shown in FIG. 9, the LDPC codes of various parity check matrices can be decoded as long as the message memory 104 (FIG. 9), the FIFO memory 155 of the variable node calculator 102 (FIG. 10), and the FIFO memory 127 and the FIFO memory 133 of the check node calculator 103 (FIG. 11) have the sizes large enough for decoding.
If decoding is made by repetitively using the decoding apparatus shown in FIG. 9, check not computation and variable node computation needs to be executed alternately, so that a clock count twice the number of message is required for one operation of decoding. However, in the case of LDPC codes having a structure of parity check matrix, providing P node calculators can execute decoding by a clock count of 1/P.
The following describes a decoding apparatus configured to decode LDPC codes having a structure for executing node operations in parallel with each LDPC constituting matrix. It should be noted that this operation will be hereafter referred to partly parallel decoding.
LDPC codes subject to partly parallel decoding can be expressed in a matrix made up of combinations of two or more constituent matrices. The constituent matrix includes a P×P identity matrix, a matrix with one or more of is that are components of this identity matrix being 0 (hereafter appropriately referred to as a quasi-identity matrix), a matrix obtained by cyclically shifting identity matrix or quasi-identity matrix (hereafter appropriately referred to as a shift matrix), a sum of two or more (plural) of identify matrix, quasi-identity matrix, and shift matrix (hereafter appropriately referred to as a sum matrix), and a P×P 0 matrix. It should be noted that the parity check matrix having the above-mentioned structure is referred to as a P×P structured parity check matrix and the LDPC code that is expressed in the P×P structured parity check matrix are referred to as “P-code.”
In decoding a P-code, P check node operations and P variable node operations can be executed at the same time.
For example, referring to FIG. 12, there is shown an example of P×P structured parity check matrix H with P=6. To be more specific, parity check matrix H shown in FIG. 12 is indicative of one example of a matrix made up of combinations of two or more constituent matrices that are 6×6 identity matrix, 6×6 quasi-identity matrix, 6×6 shift matrix, 6×6 sum matrix, and 6×6 0 matrix. It should be noted that this code has a coding ratio of 2/3 and a code length 108.
Further, the following describes the partly parallel decoding as an example in which both check node operation and variable node operation can be processed alternately by one circuit instead of using separate variable node calculator and check node calculator.
Referring to FIG. 13, there is shown an exemplary configuration of a decoding apparatus that executes partly parallel decoding by use of six node calculators in “P=6 code” decoding. It is assumed in this example of FIG. 13 that the above-described code shown in FIG. 12 be decoded as “P=6 code.”
The decoding apparatus shown in FIG. 13 has a received-value memory 200, a message memory 201, a message calculating block 202 including a P=6 node calculators 210-1 through 210-6, a control block 203, a shift block 204, and a decoding result memory 205.
It should be noted that the node calculators 210-1 through 210-6 will hereafter be generically referred to as a node calculator 210 unless otherwise required.
Receive data (LDPC code) D200 that is a logarithmic likelihood ratio indicative of the likelihood of 0 (or 1) of code obtained by receiving transmitted LDPC codes is supplied to the received-value memory 200 that stores this data D200.
At the time of a variable node operation, the received-value memory 200 reads the stored receive data in accordance with a control signal supplied from the control block 203 and supplies the receive data to the node calculator 210 of the message calculating block 202 as received data D201.
The message memory 201 stores or reads message data as required under the control of the control block 203. To be more specific, the message memory 201 appropriately supplies messages D202, D203 to the node calculator 210 and appropriately stores message D205 supplied from the shift block 204. The message memory 201 is configured by two or more independently controllable memories so as to simultaneously read two pieces of message data.
Each node calculator 210 of the message calculating block 202 can execute processing by switching between variable node operation and check node operation.
To be more specific, at the time of a variable node operation, the node calculator 210 executes a variable node operation in accordance with equation (1) for example by use of messages D202, D203 supplied from the message memory 201 and receive data D201 supplied from the received-value memory 200 and supplies message (variable node message) vi obtained as a result of this variable node operation to the shift block 204 as message D204.
At the time of a check node operation, the node calculator 210 executes a check node operation in accordance with equation (7) for example by use of messages D202, D203 supplied from the message memory 201 and supplies message (check node message) ui to the shift block 204 as message D204.
If message D204 is supplied from the message calculating block 202, information indicative how many identity matrices for example providing the source in the parity check matrix shown in FIG. 12 were cyclically shifted by the edge corresponding to message D204 is supplied from the control block 203 to the shift block 204. On the basis of the supplied information, the shift block 204 executes a cycle shift operation so as to sort message D204 and supplies a result of this operation to the message memory 201 as message D204.
In FIG. 13, in order to operate six variable nodes per constituent matrix in parallel, P=6 node calculators 210-1 through 210-6 are arranged. For example, if the number of bits m per item of receive data is 6, then the size of the constituent matrix becomes 6×6, so that the received-value memory 200 is made up of a RAM of 36 bits per word, for example. Because node operations are executed in parallel for each constituent matrix, the data for the constituent matrix are simultaneously transmitted from the received-value memory 200 to the node calculators 210-1 through 210-6.
Referring to FIG. 14, there is shown an exemplary configuration of the node calculator 210 shown in FIG. 13 that alternately executes a variable node operation in accordance with equation (1) and a check node operation in accordance with equation (7).
The node calculator 210 has three input ports P301, P302, P303 through which messages (data) are supplied from the outside and two output ports P304, P305 through which messages (data) are outputted to the outside.
To be more specific, the input port P301 is supplied with receive data read from the received-value memory 200 shown in FIG. 13. The input ports P302, P303 are supplied with messages D202, D203 read from the message memory 201, respectively. A message D321 to be described later is outputted through the output port P304 to be supplied to the message memory 201 as an output message D204. At the final stage of the decoding, a message D308 to be described later is outputted through the output port P305 to be supplied to the decoding result memory 205 as a decoding result.
The node calculator 210 shown in FIG. 14 has selectors 301, 311, 316. If these selectors 301, 311, 316 select the “v” side, the node calculator 210 shown in FIG. 14 executes a variable node operation. On the other hand, if these selectors select the “c” side, the node calculator 210 shown in FIG. 14 executes a check node operation.
First, the node calculator 210 shown in FIG. 14 will be described from the viewpoint of processing to be executed for a variable node operation.
Messages D202 from check nodes corresponding to one column of the parity check matrix supplied from the message memory 201 are entered, one by one, through the input port P302 as messages D301 (messages uj) and entered in an adder 302 through the selector 301 as message D306. In the adder 302, the data D307 stored in a register 303 is added to the message D306 and a resultant added value is stored in the register 303 again. Thus, the data D307 becomes an integrated value of messages D301 (messages uj).
When messages D301 (messages uj) for one column have been integrated, a resultant integrated value D307 (Σuj from j=1 to dv) is stored in a register 305 through the selector 304.
At the same time, the same value as the messages D301 (messages uj) entered in the port P302 is read from the message memory 201 again as message D203 to be entered again through the input port P303 as a delay input message D302.
The delay input message D302 passes a selector 311 to be subtracted in a subtractor 312 from the integrated message D308 stored in the register 305 and the subtracted value D316 (Σuj from j=1 to dv−1) is supplied to an adder 313. The adder 313 is also supplied with receive data D201 (u0i) from the received-value memory 200 through the input port P301 as received data D300. In the adder 313, the supplied receive data D300 (u0i) is added to the subtracted value D316 (Σuj from j=1 to dv−1) and resultant added value D317 ((Σuj+u0i from j=1 to dv−1) provides a message D321 through the selector 316. This message D321 is outputted from the output port P304 as an output message D204 to be supplied to the shift block 204.
In other words, the node calculator 210 shown in FIG. 14 realizes the operation of equation (1) by calculating the messages to the edges to be obtained by subtracting the messages from the check nodes to be obtained from a sum of the messages from all check nodes connected to the variable nodes and the receive data.
The following describes the node calculator 210 shown in FIG. 14 from the viewpoint of processing to be executed for a check node operation.
Messages D202 from the variable nodes corresponding to one row of the parity check matrix supplied from the message memory 201 are entered, one by one, through the input port P302 as messages D301 (messages vi) and absolute value D303 (|vi|) thereof is supplied to a LUT 300.
By use of the value entered therein as argument X, the LUT 300 outputs an operation result of nonlinear function φ(X) in the check node operation of equation (7). To be more specific, the LUT 300 reads operation result D305 (φ(|vi|)) obtained by executing nonlinear function φ(|vi|) on the supply of absolute value D303 (|vi|).
This operation result D305 (φ(|vi|)) is entered in the adder 302 through the selector 301 as a message D306. In the adder 302, data D307 stored in the register 303 is added to this message D306 and a resultant added value is stored in the register 303 again. Thus, the data D307 becomes the integrated value of operation result D305 (φ(|vi|)).
When the operation results D305 (φ(|vi|)) of the messages D301 (message vi) for one row have been integrated, resultant integrated value D307 (Σuj from i=1 to dc) passes the selector 304 to be stored in the register 305.
The same value as the messages D301 (messages vi) entered through the port P302 is read again from the message memory 201 as message D203 to be entered again through the input port P303 as a delay input message D302.
Like the operation of the LUT 300 on the input message D301, an LUT 310 executes an operation of nonlinear function φ(|vi|) on the supply of the absolute value D312 (|vi|) of the delay input message D302 and an operation result D314 (φ(|vi|)) thereof is read.
This operation result (φ(|vi|)) is entered in the subtractor 312 through the selector 311 as a message D315.
In the subtractor 312, the message D315 is subtracted from the integrated message D308 stored in the register 305 and a resultant subtracted value (Σφ(|vi|) from i=1 to dc−1) is supplied to a LUT 314.
By use of the value entered therein as argument X, the LUT 314 outputs an operation result of inverse function φ−1(X) of nonlinear function φ(X) in the check node operation of equation (7). To be more specific, the LUT 314 outputs operation result D381 (φ−1(Σφ(|vi|))) obtained by execution an operation of inverse function φ−1(Σφ(|vi|)) on the supply of subtracted value D316 (Σφ(|vi|) from i=1 to dc−1) from the subtractor 312.
Concurrently with the above-mentioned processing, an exclusive OR operation is executed in an EXOR circuit 306 between the sign bit D304 (sign(vi)) indicative of plus or minus of each message D301 and the value D310 stored in a register 307 and an operation result D309 of this operation is stored in the register 307 again.
When the sign bits for one row have been integrated in the register 307, a resultant integrated value D310 (Π sign(vi) from i=1 to dc) is stored in a register 309 through a selector 308.
The value D304 (sign(vi)) used for the integration is entered from the input port P303 again as a sign bit 313 of a delay input message to be supplied to an EXOR circuit 315. Then, an exclusive OR operation is executed in the EXOR circuit 315 between this sign bit D313 and an integrated value D311 in the register 309 and an operation result, namely, Π sign(vi) from i=1 to dc−1 is outputted as a sign bit D319.
Finally, a value D320 obtained by adding this sign bit D319 to the operation result D318 (φ−1(Σφ(|vi|))) of the LUT 314 becomes a message D321. This message D312 is outputted from the output port P304 to the shift block 204 as an output message D204.
In other words, the node calculator 210 shown in FIG. 14 realizes the operation of equation (7) by subtracting the messages from variable nodes to be obtained from a sum of the messages from all variable nodes connected to the check nodes.
Also, in the node calculator 210 shown in FIG. 14, at the final stage of decoding (for example, the variable node operation to be executed last among the variable node operations and the check node operations that are repetitively executed by predetermined repetitive decoding count N), the operation of equation (5) is executed instead of the variable node operation of equation (1) and an operation result thereof, namely, the output data D308 from the register 305, is outputted from the output port P305 as a decoding result to be supplied to the decoding result memory 205.
Meanwhile, the variable node operation (equation (1)) and the check node operation (equation (7)) can be replaced by u′j=φ(|uj|)×sign(uj) to be rewritten to equation (9) and equation (10) below, respectively.
                    [                  Equation          ⁢                                          ⁢          9                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          (                                                                    ϕ                                          -                      1                                                        ⁡                                      (                                                                                        u                        j                        ′                                                                                    )                                                  ×                                  sign                  ⁡                                      (                                          u                      j                      ′                                        )                                                              )                                                          (        9        )                                [                  Equation          ⁢                                          ⁢          10                ]                                                                      u          j          ′                =                              ∑                          i              =              1                                                      d                c                            -              1                                ⁢                                    ϕ              ⁡                              (                                                                        v                    i                                                                    )                                      ×                                          ∏                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                              sign                ⁡                                  (                                      v                    i                                    )                                                                                        (        10        )            
It should be noted that φ(X)=φ−1(X). To be more specific, in each of the variable node operation (equation (9)) and the check node operation (equation (10)), operation φ(X) is executed on the absolute value of input data. Therefore, in the case of the check node operation, absolute values are integrated and an output message can be calculated by multiplying a resultant integrated value by a sign obtained separately. On the other hand, in the case of the variable node operation, an addition is executed by also including sign bits, to which receive data is added to provide an output message.
Referring to FIG. 15, there is shown an exemplary configuration of the node calculator 210 shown in FIG. 13 that alternately executes the variable node operation according to equation (9) and the check node operation according to equation (10).
The node calculator 210 has three input ports P601, P602, P603 in which messages (data) are entered from the outside and two output ports P604, P605 from which messages (data) are supplied (outputted) to the outside.
To be more specific, the receive data D201 read from the received-value memory 200 shown in FIG. 13 is supplied to the input port P601. Messages D602, D603 read from the message memory 201 are supplied to the input ports P602, P603. Then, a message D622 to be described later is outputted from the output port P604 as an output message D204 to be supplied to the message memory 201. In the final stage of decoding, a message D609 to be described later is outputted from the output port P605 to be supplied to the decoding result memory 205.
The node calculator 210 shown in FIG. 15 has selectors 601, 611, 615. If these selectors 601, 611, 615 select the “v” side, the node calculator 210 shown in FIG. 15 executes a variable node operation. On the other hand, if the selectors 601, 611, 615 select the “c” side, the node calculator 210 shown in FIG. 15 executes a check node operation.
First, the node calculator 210 shown in FIG. 15 will be described from the viewpoint of the execution of a variable node operation.
Messages D202 from check nodes corresponding to one column of the parity check matrix supplied from the message memory 201 are entered one by one through the input port P602 as messages D601 (messages u′j). A LUT 600 executes an operation of φ−1(X) with absolute value (|u′j|) thereof being argument X and supplies a value D606 (message uj) obtained by multiplying an operation result D605 (|uj|) by sign bit D604 (sign(uj)) to an adder 602 through the selector 601 as a value D607. This value D607 is added in the adder 602 to the data D608 stored in a register 603 to be stored in the register 603 again. Thus, the data D608 becomes an integrated value of message D607 (message uj).
When messages D607 (messages uj) for one column have been integrated, a resultant integrated value D608 (Σuj from j=1 to dv) is supplied to a register 605 through a selector 604.
The same value as the message D601 (message u′j) entered in the port P602 is read from the message memory 201 as a message D203 to be entered again through the input port P603 as a delay input message D602.
Of the delay input message D602, an operation φ−1(X) is executed by LUT 610 with absolute value D613 (|u′j|) being argument X and value D616 (message uj) obtained by multiplying an operation result D615 (|uj|) thereof by sign bit D614 (sign(uj)) is supplied to a subtractor 612 through the selector 611 as value D617.
In the subtractor 612, the above-mentioned value D617 is subtracted from the integrated message D609 stored in the register 605 and a resultant subtracted value D618 (Σuj from j=1 to dv−1) is supplied to an adder 613. The adder 613 is also supplied with the receive data D201 (u0i) from the received-value memory 200 through the input port P601 as receive data D600. In the adder 613, the receive data 600 (u0i) is added to the subtracted value D618 (Σuj from j=1 to dv−1) and a resultant added value (Σuj+u0i) from j=1 to dv−1) becomes a message D622 through the selector 615. This message D622 is outputted from the output port P604 as an output message D204 to be supplied to the shift block 204.
In other words, the node calculator 210 shown in FIG. 15 realizes the operation of equation (9) by calculating messages to the edges to be obtained by subtracting messages from the check nodes to be obtained from a sum of the messages from all check nodes connected to variable nodes and the receive data.
The following describes the node calculator 210 shown in FIG. 15 from the viewpoint of the execution of a check node operation.
Messages D202 from the variable nodes corresponding to one column of the parity check matrix supplied from the message memory 201 are entered one by one through the input port P602 as messages D601 (messages Vi) and absolute value (|vi|) thereof is supplied to the LUT 600. The LUT 600 executes an operation φ(X) with this absolute value (|vi|) being an argument X and supplies an operation result (φ|vi|) thereof to the adder 602 through the selector 601 as a value D607. This value D607 is added in the adder 602 to data D608 stored in the register 603 to be stored in the register 603 again. Thus, the data D608 becomes an integrated value of operation result D607 (φ(|vi|)).
When operation results D607 of the messages D601 (messages vi) for one row have been integrated, the integrated value (Σφ(|vi|) from i=1 to dc) is stored in the register 605 through the selector 604.
The same value as the message D601 (message vi) entered in the port P602 is read from the message memory 201 as a message D203 to be entered again through the input port P603 as a delay input message D602.
Like the operation by the LUT 600 on the input message D601, a LUT 610 executes an operation of φ(X) on the delay input message D602 with the absolute value D613 (|vi|) being argument X to read out a operation result D615 (φ(|vi|)) thereof.
This operation result D615 (φ(|vi|)) is entered in the subtractor 612 through the selector 611 as a message D617.
In the subtractor 612, the message D617 is subtracted from the integrated message D609 stored in the register 605 and a resultant subtracted value D618 (Σφ(|vi|) from i−1 to dc−1) is outputted.
Concurrently with the above-mentioned processing, an exclusive OR operation is executed by an EXOR circuit 606 between the sign bit D604 (sign(vi)) indicative of the plus or minus of each message D601 and the value D611 stored in a register 607 and an operation result D610 thereof is stored in the register 607 again.
When the sign bits for one row have been integrated in the register 607, a resultant integrated value D611 (Π sign (vi) from i=1 to dc) is stored in a register 609 through a selector 608.
The value D604 (sign(vi)) used for the integration is entered from the input port P603 again as a sign bit D614 of the delay input message into an EXOR circuit 614. An exclusive OR operation is executed by the EXOR circuit 614 between this sign bit D614 and the integrated value in the register 609. A result of this operation, namely, Πsign(vi) from i=1 to dc−1, is outputted as a sign bit D620.
Finally, a value D621 obtained by adding this sign bit D620 to subtracted value D618 (Σφ(|vi|) from i=1 to dc−1) from the subtractor 612 becomes a message D622 through the selector 615. This message D622 is outputted from the output port P604 as an output message D204 to be supplied to the shift block 204.
In other words, the node calculator 210 shown in FIG. 15 realizes the operation of equation (10) by subtracting messages from the variable nodes to be obtained from a sum of messages from all variable nodes connected to check nodes.
Also, in the node calculator 210 shown in FIG. 15, at the final stage of decoding (for example, the variable node operation to be executed last among the variable node operations and the check node operations that are repetitively executed by predetermined repetitive decoding count N), an operation in accordance with an equation obtained by rewriting equation (5) like the equation (9) is executed instead of the variable node operation of equation (9) and a result of this operation, namely, output data D609 from the register 605, is outputted from the output port P605 as a decoding result to be supplied to the decoding result memory 205 shown in FIG. 13.
Further, the variable node operation (equation (1)) and the check node operation (equation (7)) can be rewritten to equation (12) and equation 13) below, respectively, by replacing v′i=φ(|vi|)×sign(vi). It should be noted that, in order to simplify the comparison with equation (12), equation (11) has been obtained by rewriting equation (1) again.
                    [                  Equation          ⁢                                          ⁢          11                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        11        )                                [                  Equation          ⁢                                          ⁢          12                ]                                                                      v          i          ′                =                              ϕ            ⁡                          (                                                                v                  i                                                            )                                ×                      sign            ⁡                          (                              v                i                            )                                                          (        12        )                                [                  Equation          ⁢                                          ⁢          13                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                                                        v                    i                    ′                                                                                )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                  ′                                )                                                                        (        13        )            In the above equations, φ(X)=φ−1(X). Namely, in each of the variable node operation (equation (12)) and the check node operation (equation (13)), an operation of φ(X) is executed on the absolute value of input data. Therefore, in the case of the check node operation, an output message can be calculated by integrating the absolute values of input data, executing an operation of φ(X) on the result of the integration, and then multiplying the result of this operation by a sign bit obtained separately. On the other hand, in the case of the variable node operation, the input data is integrated including also a sign bit, the receive data is added to the result of the integration, an operation of φ(X) is executed on the absolute value thereof, and the result of this operation is multiplied by the sign bit to provided an output message.
Referring to FIG. 16, there is shown an exemplary configuration of the node calculator 210 shown in FIG. 13 in which a variable node operation according to equation (12) and a check node operation according to equation (13) are alternately executed.
The node calculator 210 has three input ports P701, P702, P703 in which messages (data) are entered from the outside and two output ports P704, P705 from which messages (data) are supplied (outputted) to the outside.
To be more specific, the receive data D201 read from the received-value memory 200 shown in FIG. 13 is supplied to the input port P701. The messages D702 and D703 read from the message memory 201 are supplied to the input ports P702 and P703, respectively. Message D722 to be described later is outputted from the output port P704 as output message D204 to be supplied to the message memory 201. In the final stage of decoding, a message D707 to be described later is outputted from the output port P705 as a result of the decoding to be supplied to the decoding result memory 205.
The node calculator 210 shown in FIG. 16 has selectors 700, 705, 712, 715. If these selectors 700, 705, 712, 715 select the “v” side, the node calculator 210 shown in FIG. 16 executes a variable node operation. On the other hand, if the selectors 700, 705, 712, 715 select the “c” side, the node calculator 210 shown in FIG. 16 executes a check node operation.
First, the node calculator 210 shown in FIG. 16 will be described from the viewpoint of the execution of a variable node operation.
Messages D202 from the check nodes corresponding to one column of the parity check matrix supplied from the message memory 201 are entered one by one through the input port P702 as messages D701 (messages uj) to be entered in an adder 701 through the selector 700 as a message D705. In the adder 701, data D706 stored in a register 702 is added to the message D705 to be stored in the register 702 again. Thus, the data D706 becomes an integrated value of the messages D701 (messages uj).
When the messages D701 (messages uj) for one column have been integrated, a resultant integrated value D706 (Σuj from j=1 to dv) is stored in a register 704 through the selector 703.
The same value as the message D701 (message uj) entered in the port P702 is read again from the message memory 201 as a message D203 to be entered through the input port P703 as a delay input message D702.
The delay input message D702 passes the selector 705 to be subtracted in a subtractor 710 from the integrated message D707 and a resultant subtracted value D714 (Σuj from j=1 to dv−1) is supplied to an adder 711. Also, the receive data D201 (u0i) from the received-value memory 200 is supplied to the adder 711 through the input port P701 as receive data D700. Therefore, in the adder 711, the receive data D700 (u0i) is added to the subtracted value D714 (Σui from j=1 to dv−1) and the absolute value D716 (|vi|) of a resultant added value (Σuj+u0i=vi from j=1 to dv−1) is becomes an absolute value D718 (|vi|) through the selector 712 to be supplied to a LUT 713. In the LUT 713, an operation of φ(X) is executed with argument X being the absolute value D718 (|vi|) and a result of this operation D719 (φ|vi|) is outputted.
Concurrently with the above-mentioned processing, the sign bit D717 (sign(vi)) of the added value D715 (vi) from the adder 711 becomes a sign bit D721 through the selector 715. This sign bit D721 is multiplied by the operation result D719 (φ|vi|) of the LUT 713 to provide a message D722 (φ|vi|×sign(vi)). This message D722 is outputted from the output port P704 as an output message D204 to be supplied to the shift block 204.
In other words, the node calculator 210 shown in FIG. 16 realizes the operation of equation (12) by calculating messages to the edges to be obtained by subtracting messages from the check nodes to be obtained from a sum of the messages from all check nodes connected to variable nodes and the receive data.
The following describes the node calculator 210 shown in FIG. 16 from the viewpoint of the execution of a check node operation.
Messages D202 from the variable nodes corresponding to one row of the parity check matrix supplied from the message memory 201 are entered one by one through the input port P702 as messages D701 (messages v′i) and the absolute value D703 (|v′i|) is entered in the adder 701 through the selector 700 as the absolute value D705. In the adder 701, the data D706 stored in the register 702 is added to this absolute value D705 to be stored in the register 702 again. Thus, the data D706 becomes an integrated value of absolute value D703 (|v′i|).
When the absolute values D703 (|v′i|) of the messages D701 (message v′i) for one row have been integrated, a resultant integrated value D706 (Σ|v+i| from i=1 to dc) is stored in the register 704 through the selector 703.
The same value as the message D701 (message v′i) entered in the port P702 is read from the message memory 201 as a message D203 to be entered again through the input port P703 as a delay input message D702.
The absolute value D711 (|v′i|) of the delay input message D702 passes the selector 705 to be subtracted in the subtractor 710 from the integrated message D707 stored in the register 704 and a resultant subtracted value D714 (Σ|v′i| from i−1 to dc−1) is supplied to a LUT 713 through the selector 712 as a subtracted value D718. In the LUT 713, an operation of φ−1(X) is executed with the subtracted value D718 (Σ|v′i| from i−1 to dc−1) being argument X and an operation result D719 (φ−1(Σ|v′i| from i=1 to dc−1) is read.
Concurrently with the above-mentioned processing, an exclusive OR operation is executed in an EXOR circuit 706 between the sign bit D704 (sign(v′i) indicative of plus or minus of each message D701 and the value D709 stored in a register 707. An operation result D708 thereof is stored in the register 707 again.
When the sign bits for one row have been integrated in the register 707, a resultant integrated value D709 (Π sign(v′i) from i=1 to dc) is stored in a register 709 through the selector 708.
The value D704 (sign(v′i)) used for the integration is entered again from the input port P703 as the sign bit D712 of the delay input message into an EXOR circuit 714. An exclusive OR operation is executed by the EXOR circuit 714 between this sign bit D712 and the integrated value D710 in the register 709 and a result of this operation, namely, Π sign(v′i) from i=1 to dc−1, is outputted as a sign bit D720. This sign bit D720 becomes a sign bit D721 through the selector 715.
Finally, a value obtained by adding this sign bit D721 to the operation result D719 (φ−1(Σ|v′i|) from i=1 to dc−1) provides a message D722. This message D722 is outputted through the output port P704 as an output message D204 to be supplied to the decoding result memory 205.
In other words, the node calculator 210 shown in FIG. 16 realizes the operation of equation (13) by subtracting the messages from the variable nodes to be obtained from a sum of all variable nodes connected to check nodes.
Also, in the node calculator 210 shown in FIG. 16, at the final stage of decoding (for example, the variable node operation to be executed last among the variable node operations and the check node operations that are repetitively executed by predetermined repetitive decoding count N), an operation in accordance with an equation obtained by rewriting equation (5) like the equation (12) is executed instead of the variable node operation of equation (12) and a result of this operation, namely, output data D707 from the register 704, is outputted from the output port P705 as a decoding result to be supplied to the decoding result memory 205 shown in FIG. 13.